package code;
import java.util.ArrayList;
public class Permutation {

    public ArrayList<String> re = new ArrayList<>();
    public void swap(char[] l,int i,int j){
        char t = l[i];
        l[i] = l[j];
        l[j] = t;
    }

    public boolean isNeedSwap(char[] l,int i, int j){
        for(int k=i;k<j;k++) {
            if (l[k] == l[j]) {
                return false;
            }
        }
        return true;

    }

    public ArrayList<String> Solution(String str) {
        char[] list = str.toCharArray();
        per(list,0,list.length-1);
        this.re.sort(String::compareTo);
        return this.re;
    }


    public void per(char[] list,int start,int end){
        if(start == end ){
            this.re.add(String.valueOf(list));
        }else {
            for (int i=start;i<=end;i++){
                if(isNeedSwap(list,start,i)){
                    swap(list,start,i);
                    per(list,start+1,end);
                    swap(list,start,i);
                }
            }
        }
    }

    public static void main(String[] argv){
        Permutation permutation = new Permutation();
        for(String s:permutation.Solution("abcb")){
            System.out.println(s);
        }

    }
}
